package com.code.nowcoder;

import com.code.nowcoder.utils.Point;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/7/28 18:15
 */
public class The85 {
    /**
     * 能回到1号点返回 Yes，否则返回 No
     *
     * @param param int整型一维数组 param[0] 为 n，param[1] 为 m
     * @param edge Point类一维数组 Point.x , Point.y 分别为一条边的两个点
     * @return string字符串
     */
    boolean[] marked;
    int m;
    Point[] edge;

    public String solve(int[] param, Point[] edge) {
        // write code here
        m = edge.length;
        if (param[1] >= 100000) return "No";
        marked = new boolean[m];
        this.edge = edge;
        for (int i = 0; i < m; i++) {
            if (edge[i].x == 1 || edge[i].y == 1) {
                if (dfs(edge[i], 1, i, 1)) return "Yes";
            }
        }
        return "No";
    }

    /**
     *  判断是否有回路
     * @param point 当前传入的点
     * @param len 最大长度
     * @param index 当前点的索引坐标
     * @param p 上个节点的传入值
     * @return 是否有回路
     */
    public boolean dfs(Point point, int len, int index, int p) {
        if (len == m) return point.y == 1 || point.x == 1;
        if (len > 1 && ((point.x == 1) || (point.y) == 1)) return true;
        marked[index] = true;
        for (int i = 0; i < m; i++) {
            if ((edge[i].x == p || p == edge[i].y) && !marked[i]) {
                if (edge[i].x == p) {
                    if (dfs(edge[i], len + 1, i, edge[i].y)) return true;
                }
                if (edge[i].y == p) {
                    if (dfs(edge[i], len + 1, i, edge[i].x)) return true;
                }
            }
        }
        marked[index] = false;
        return false;
    }
    // [7,11],[(3,2),(5,1),(1,6),(6,4),(7,2),(7,4),(4,2),(1,3),(6,3),(3,7),(5,6)]


}
